use::std::collections::HashMap;
use std::vec;





pub fn group_anagrams(strs:Vec<&str>) -> Vec<Vec<String>>
{

    let mut vecs: Vec<Vec<String>> = Vec::new();
    let mut used: Vec<bool> = vec![false; strs.len()];// 返回元素的数量

    // 遍历strs中的元素
    for i in 0..strs.len(){
        let mut temp: Vec<String> = Vec::new();

        // 这个元素未被使用，则进行：
        if !used[i]{

            temp.push(strs[i].to_string());

            // 遍历后边的元素内容
            for j in i+1..strs.len(){

                let mut is_anagram = true;
                // 如果判断 当前的字符串后后边的字符串的长度不同，则忽略 再检查下一个
                if strs[i].len() != strs[j].len(){
                    continue;
                }
                
                let mut map = HashMap::new();

                // 遍历当前字符串，填入哈希表
                for c in strs[i].chars(){
                    let count = map.entry(c).or_insert(0);
                    *count += 1;
                } 
                // 遍历 下一个字符串，在哈希表中检查是否有对应键值
                for c in strs[j].chars()  {
                    let count = map.entry(c).or_insert(0);
                    *count -= 1;
                    
                    if *count < 0{
                        is_anagram = false;
                        break;
                    }
                }

                // 如果找到了匹配的，则将下一个字符串设为已经使用，并填入二维数组中。
                if is_anagram{
                    used[j] = true;
                    temp.push(strs[j].to_string());
                }

            }

        }

        if !temp.is_empty(){
            vecs.push(temp);
        }
    }

    return vecs;

}


/**
 * 代码12-13
 */
pub fn group_anagrams_new(strs:Vec<String>) -> Vec<Vec<String>>
{
    let mut vecs:Vec<Vec<String>> = Vec::new();
    // 创建一个哈希表：键是String，值是 字符串动态数组
    let mut map: HashMap<String,Vec<String>> = HashMap::new();

    for i in 0..strs.len()
    {
        // 建立一个26个i32元素的数组
        let mut count = [0; 26];

        // 遍历 第i个字符串的字符
        for c in strs[i].chars()
        {
            // 把每个字符转为数字
            let index: usize = (c as u32 - 'a' as u32) as usize;
            // 然后加入数组对应位置
            count[index] += 1;
        }

        // 建一个 空的动态数组
        let mut chars = vec![];

        // 把上方的数组每一个元素转为字符串并连接# 分隔。
        for i in 0..count.len(){
            chars.push(count[i].to_string() + "#");
        }

        // 拼成一个新的字符串
        let key: String = chars.into_iter().collect();

        // 从哈希表中取得键对应的值，这个键是刚刚组成的新的字符串。
        let value = map.get(&key);

        if value != None{
            // 如果键有值，就更新：把当前的字符串添加到v这个字符串动态数组中，然后把这个数组更新到哈希表中。
            let mut v = value.unwrap().to_vec();
            v.push(strs[i].clone());
            map.insert(key, v);
        }
        else {
            // 如果键没有值，就插入
            let v = vec![strs[i].clone()];
            map.insert(key, v);
        }
    }

    for val in map.values() {
        vecs.push((*val).clone());
    }

    return  vecs;

}


pub fn group_anagrams_new_2(strs:Vec<String>) -> Vec<Vec<String>>
{
    let mut vecs: Vec<Vec<String>> =Vec::new();

    let mut map: HashMap<String, Vec<String>> = HashMap::new();

    for i in 0..strs.len(){
        let mut chars = vec![];

        // 把字符串转为字符填入数组里
        for c in strs[i].chars(){
            chars.push(c);
        }
        // 然后把字符数组排序
        chars.sort();

        let key = chars.into_iter().collect();

        let value = map.get(&key);

        if value != None{
            // 取出的是 Option<&>,用unwrap去掉Option，然后用 to_vec 去掉&,得到 Vec<String>
            let mut v = value.unwrap().to_vec();
            v.push(strs[i].clone());
            map.insert(key, v);
        }
        else {
            let v = vec![strs[i].clone()];
            map.insert(key, v);
        }
    }

    for val in map.values(){
        vecs.push(val.to_vec());
    }

    return vecs;

}

